package datastructure.day04;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author Gan
 * @Date 2021/5/4 16:44
 * @Description: 链表实现
 */
public class MyBSTree<T extends Comparable<T>> {
    //树的根节点
    private Node root;
    //树的结点个数
    private int size;

    public boolean add(T t) {
        //不允许插入null
        if (t == null) {
            throw new IllegalArgumentException("Parameter can not be null");
        }
        //若原来就是空树
        if (size == 0) {
            root = new Node(null, t, null);
            size++;
            return true;
        }
        //要插入的值既不是null，树也不是空
        //mid是遍历树的指针，midFather是mid父节点指针
        Node mid = root;
        Node midFather = null;
        int data = 0;
        while (mid != null) {
            data = t.compareTo(mid.value);
            if (data > 0) {
                midFather = mid;
                mid = mid.right;
            } else if (data < 0) {
                midFather = mid;
                mid = mid.left;
            } else {
                //不储存相同的值
                return false;
            }
        }
        //到了尾部mid后没有结点了
        if (data > 0) {
            midFather.right = new Node(null, t, null);
        } else {
            midFather.left = new Node(null, t, null);
        }
        size++;
        return true;
    }

    public boolean contains(T t) {
        if (t == null) {
            throw new IllegalArgumentException("value can not be null!");
        }
        Node mid = root;
        int data;
        while (mid != null) {
            data = t.compareTo(mid.value);
            if (data > 0) {
                mid = mid.right;
            } else if (data < 0) {
                mid = mid.left;
            } else {
                return true;
            }
        }
        return false;
    }

    public boolean remove(T t) {
        if (t == null) {
            throw new IllegalArgumentException("illegal option.");
        }
        Node mid = root;
        Node midFather = null;
        int data = 0;
        while (mid != null) {
            data = t.compareTo(mid.value);
            if (data > 0) {
                midFather = mid;
                mid = mid.right;
            } else if (data < 0) {
                midFather = mid;
                mid = mid.left;
            } else {
                break;
            }
        }
        if (mid == null) {
            System.out.println("没有找到要删除的结点");
            return false;
        }
        //若删除的是双分支结点，用right树中最小的结点代替
        if (mid.left != null && mid.right != null) {
            Node min = mid;
            Node minFather = midFather;
            while (min.left != null) {
                min = min.left;
            }
            mid.value = min.value;
            mid = min;
            midFather = minFather;
        }
        //找到不为空的左子树或者右子树，若全为空则ch为null
        Node ch = mid.left != null ? mid.left : mid.right;
        //若删除的是根节点而且还是单分支的,mid指针不会往下遍历，所以midFather是null
        if (midFather == null) {
            root = ch;
            size--;
            return true;
        }
        //删除操作，本质是上移
        if (mid == midFather.left) {
            midFather.left = ch;
        } else {
            midFather.right = ch;
        }
        size--;
        return true;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean remove1(Node root, T t) {
        int oldSize = size;
        root = remove2(root, t);
        return size < oldSize;
    }

    private Node remove2(Node root, T t) {
        if (t == null) {
            return null;
        }
        int data = t.compareTo(root.value);
        if (data > 0) {
            root = remove2(root.right, t);
        } else if (data < 0) {
            root = remove2(root.left, t);
        } else {
            if (root.right != null && root.left != null) {
                //若要被删除的是双分支结点，获取右子树最小的值来代替要被删除的结点
                Node min = root.right;
                while (min.left != null) {
                    min = min.left;
                }
                //值替换
                root.value = min.value;
                root.right = remove2(root.right, min.value);
                //若删除的是单分支结点
                Node node = root.left != null ? root.left : root.right;
                return node;
            }
        }
        return root;

    }

    //用递归实现前序遍历
    public List<T> preOrder() {
        List<T> list = new ArrayList<>();
        preOrder(list, root);
        return list;
    }

    private void preOrder(List<T> list, Node node) {
        if (node == null) {
            return;
        }
        // 前序遍历
        list.add(node.value);
        preOrder(list, node.left);
        preOrder(list, node.right);
    }

    //用栈实现前序遍历
    public List<T> preOrder1() {
        if (root == null) {
            return null;
        }
        //保存遍历结果
        List<T> list = new ArrayList<>();
        //new一个栈用来储存结点
        Stack<Node> stack = new Stack<>();
        //根节点入栈
        stack.push(root);
        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            //尾插法
            list.add(pop.value);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return list;
    }

    //  建树: 给定前中序, 或者给定中后序,  构建出一棵二叉树
    //  中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //  后序 [-20, -25, -50, -10, -5, 7, 2, 25, 30, 100, 10, 1]
    public void buildTreeByInAndPostOrder(List<T> inOrder, List<T> postOrder) {
        root = buildTreeByInAndPostOrder2(inOrder, postOrder);
        size = inOrder.size();
    }

    private Node buildTreeByInAndPostOrder2(List<T> inOrder, List<T> postOrder) {
        if (inOrder.size() == 0)
            return null;
        if (inOrder.size() == 1)
            return new Node(null, inOrder.get(0), null);
        // 找根结点: 后序的最后一个元素
        T value = postOrder.get(postOrder.size() - 1);
        // 获得根节点在中序的位置
        int index = inOrder.indexOf(value);// 根据内容查找下标

        // 左子树的中序(中序中切割): 0 ~ index-1
        // 左子树的后序(后序中切割): 0 ~ index -1

        // 右子树的中序(中序中切割): index + 1 ~ size -1
        // 右子树的后序(后序中切割): index ~ size - 2

        // left
        List<T> leftInOrder = inOrder.subList(0, index);// 包左不包右
        List<T> leftPostOrder = postOrder.subList(0, index);// 包左不包右

        // right
        List<T> rightInOrder = inOrder.subList(index + 1, inOrder.size());// 包左不包右
        List<T> rightPostOrder = postOrder.subList(index, postOrder.size() - 1);// 包左不包右

        // 构建这次递归的根节点
        Node node = new Node(null, value, null);
        // 用递归方法处理, 获得左子树
        node.left = buildTreeByInAndPostOrder2(leftInOrder, leftPostOrder);
        // 用递归方法处理, 获得右子树
        node.right = buildTreeByInAndPostOrder2(rightInOrder, rightPostOrder);

        return node;
    }

    //  中序 [-50, -25, -20, -10, -5, 1, 2, 7, 10, 25, 30, 100]
    //  前序 1  -5  -10  -50  -25  -20   10  2  7  100  30  25
    public void buildTreeByInAndPreOrder(List<T> inOrder, List<T> preOrder) {
        root = buildTreeByInAndPreOrder2(inOrder, preOrder);
        size = inOrder.size();
    }

    private Node buildTreeByInAndPreOrder2(List<T> inOrder, List<T> preOrder) {
        if (inOrder.size() == 0)
            return null;
        if (inOrder.size() == 1)
            return new Node(null, inOrder.get(0), null);

        // 找根结点: 前序的第一个元素
        T value = preOrder.get(0);
        // 获得根节点在中序的位置
        int index = inOrder.indexOf(value);// 根据内容查找下标

        // 左子树的中序(中序中切割): 0 ~ index-1
        // 左子树的前序(后序中切割): 1 ~ index

        // 右子树的中序(中序中切割): index + 1 ~ size -1
        // 右子树的前序(后序中切割): index + 1 ~ size - 1

        // left
        List<T> leftInOrder = inOrder.subList(0, index);// 包左不包右
        List<T> leftPreOrder = preOrder.subList(1, index + 1);// 包左不包右

        // right
        List<T> rightInOrder = inOrder.subList(index + 1, inOrder.size());// 包左不包右
        List<T> rightPreOrder = preOrder.subList(index + 1, inOrder.size());// 包左不包右

        // 构建这次递归的根节点
        Node node = new Node(null, value, null);
        // 用递归方法处理, 获得左子树
        node.left = buildTreeByInAndPreOrder2(leftInOrder, leftPreOrder);
        // 用递归方法处理, 获得右子树
        node.right = buildTreeByInAndPreOrder2(rightInOrder, rightPreOrder);

        return node;
    }

    class Node {
        T value;
        Node right;
        Node left;

        public Node(Node right, T value, Node left) {
            this.value = value;
            this.right = right;
            this.left = left;
        }
    }
}
